package com.lsa.letcode.the60.permutationSeq;

import java.util.LinkedList;
import java.util.List;

public class Solution {
    public String getPermutation(int n, int k) {
        LinkedList<Integer> facts = new LinkedList<>();
        facts.add(1);
        facts.add(1);
        
        for (int i = 2; i < n; i++) {
        	facts.addFirst(facts.getFirst() * i);
		}
        
        LinkedList<Integer> digits = new LinkedList<>();
        for (int i = 1; i < n + 1; i++) {
			digits.add(i);
		}
                       
        StringBuilder sb = new StringBuilder();
        getPermutation(n, k - 1, sb, facts, digits);
        return sb.toString();
    }

	private void getPermutation(int n, int k, StringBuilder sb,
			LinkedList<Integer> facts, List<Integer> digits) {
		if (n == 0) {
			return;
		}
		Integer fact = facts.poll();
		int idx = k / fact;
		int digit = digits.get(idx);
		digits.remove(idx);
		sb.append(""+digit);
		int baseIdx = fact * idx;
		getPermutation(n - 1, k - baseIdx, sb, facts, digits);
	}
}